package org.hhchat.leetcode.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * Created this one by HMH on 2017/6/14.
 */
public class code322 {



    public static class Solution {
        static Map<Integer, Integer> amountDic = new HashMap<>();
        public int coinChange(int[] coins, int amount) {
            if (amount == 0) {
                return 0;
            }
            if (amountDic.containsKey(amount)) {
                return amountDic.get(amount);
            }
            int n=amount+1;
            for (int coin : coins) {
                int curr=0;
                if(amount>=coin) {
                    int next = coinChange(coins, amount - coin);
                    if(next>=0)
                        curr=next+1;
                }
                if (curr > 0) {
                    n = Math.min(curr, n);
                }
            }
            int finalCount = (n == amount + 1) ? -1 : n;
            amountDic.put(amount, finalCount);
            return finalCount;
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.coinChange(new int[]{
                2
        },1));
    }
}


//simple c++ solution

//class Solution {
//    public:
//    int coinChange(vector<int>& coins, int amount) {
//        int Max = amount + 1;
//        vector<int> dp(amount + 1, Max);
//        dp[0] = 0;
//        for (int i = 1; i <= amount; i++) {
//            for (int j = 0; j < coins.size(); j++) {
//                if (coins[j] <= i) {
//                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
//                }
//            }
//        }
//        return dp[amount] > amount ? -1 : dp[amount];
//    }
//};


// fastest dfs solution with prunning

//public class Solution {
//    //the following answer is recursive with prunning
//    public int curMin=Integer.MAX_VALUE;
//    public int coinChange(int[] coins, int amount) {
//        if(coins.length==0||amount==0)
//            return 0;
//        Arrays.sort(coins);
//        DFS(coins,coins.length-1,amount,0);
//        if(curMin==Integer.MAX_VALUE)
//            return -1;
//        return curMin;
//    }
//    public void DFS(int[]coins,int index,int amount,int count)
//    {
//        if(index==-1)
//            return ;
//        int number=amount/coins[index];
//        for(int i=number;i>=0;i--)
//        {
//            int remain=amount-coins[index]*i;
//            int newcount=count+i;
//            if(remain>0&&newcount<curMin)
//                DFS(coins,index-1,remain,newcount);
//            else if(newcount<curMin)
//                curMin=newcount;
//            else
//                break;
//        }
//    }
//}